#pragma once
#include <span>
#include <vector>

template <typename T>
void merge(std::span<T> container1, std::span<T> container2, std::span<T> dest) {
    auto it1 = container1.begin(), end1 = container1.end();
    auto it2 = container2.begin(), end2 = container2.end();
    auto itDest = dest.begin();

    while (it1 != end1 && it2 != end2) {
        if (*it1 < *it2) {
            *itDest++ = *it1++;
        }
        else {
            *itDest++ = *it2++;
        }
    }

    std::copy(it1, end1, itDest);
    std::copy(it2, end2, itDest);
}

template <typename T>
void mergeSort(std::span<T> container) {
    if (container.size() <= 1) {
        return;
    }

    auto mid = container.size() / 2;
    std::span<T> left = container.subspan(0, mid);
    std::span<T> right = container.subspan(mid);

    std::vector<T> leftVec(left.begin(), left.end());
    std::vector<T> rightVec(right.begin(), right.end());

    mergeSort(std::span{ leftVec });
    mergeSort(std::span{ rightVec });

    merge(std::span{ leftVec }, std::span{ rightVec }, container);
}